public class test02 {
    class ListNode{
        int val;
        ListNode next,prev;
        public ListNode(){}
        public ListNode(int val){
            this.val = val;
        }
    }
    class MyLinkedList {
        int size;
        ListNode head,tail;
        public MyLinkedList() {
            size = 0;
            head = new ListNode(0);
            tail = new ListNode(0);
            head.next = tail;
            tail.prev = head;
        }

        public int get(int index) {
            ListNode cur;
            if(index<0 || index>=size){
                return -1;
            }
            if(index>size/2){
                //从tail开始
                cur = tail;
                for(int i = 0;i<size-index;i++){
                    cur = cur.prev;
                }
            }else{
                cur = head;
                for(int i = 0;i<=index;i++){
                    cur = cur.next;
                }
            }
            return cur.val;
        }

        public void addAtHead(int val) {
            addAtIndex(0,val);
        }

        public void addAtTail(int val) {
            addAtIndex(size,val);
        }

        public void addAtIndex(int index, int val) {
            if(index<0 || index>size){
                return;
            }
            size++;
            ListNode pre = head;
            for(int i = 0;i<index;i++){
                pre = pre.next;
            }
            ListNode add = new ListNode(val);
            add.next = pre.next;
            add.prev = pre;
            pre.next = add;
            add.next.prev = add;
        }

        public void deleteAtIndex(int index) {
            if(index<0 || index>=size){
                return;
            }
            size--;
            ListNode pre = head;
            for(int i = 0;i<index;i++){
                pre = pre.next;
            }
            pre.next.next.prev = pre;
            pre.next = pre.next.next;
        }
    }
}
